#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

// 3. 无重复字符的最长子串
// https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

class Solution1
{
public:
    int lengthOfLongestSubstring(string s)
    {
        if(s.empty()){
            return 0;
        }
        unordered_map<char, int> recordIndexOfNum;
        int ans = 1;
        int n = s.size();
        int curLen = 0;
        for (int i = 0; i < n; i++)
        {
            char curCh = s[i];
            if (recordIndexOfNum.find(curCh) == recordIndexOfNum.end())
            {
                recordIndexOfNum[curCh] = i;
                curLen++;
                continue;
            }
            ans = max(ans, curLen);
            int pre = recordIndexOfNum[curCh] + 1;
            curLen = i - pre + 1;
            recordIndexOfNum.clear();
            while (pre <= i){
                recordIndexOfNum[s[pre]] = pre;
                pre++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        unordered_map<char, int> recordIndexOfCh;
        int n = s.size();
        int left = 0;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int curCh = s[i];
            if(recordIndexOfCh.find(curCh) != recordIndexOfCh.end() && recordIndexOfCh[curCh] >= left){
                left = recordIndexOfCh[curCh] + 1;
            }
            recordIndexOfCh[curCh] = i;
            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};

int main()
{
    string str = "pwwkew";
    Solution solution{};
    solution.lengthOfLongestSubstring(str);
    return 0;
}